/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function (head) {
  // 处理空链表的情况
  if (!head) return head;

  // 遍历链表，将所有节点存入数组
  let cur = head;
  let resultArr = [];
  while (cur) {
    resultArr.push(cur);
    cur = cur.next;
  }

  // 对数组中的节点按val值升序排序
  resultArr.sort((a, b) => a.val - b.val);

  // 创建虚拟头节点，用于构建排序后的链表
  let result = new ListNode(0);
  cur = result;

  // 遍历排序后的数组，重新连接节点
  for (let i = 0; i < resultArr.length; i++) {
    cur.next = resultArr[i];
    cur = cur.next;
  }

  // 断开最后一个节点的next指针，防止形成环
  cur.next = null;

  // 返回排序后的链表头节点（虚拟头节点的下一个节点）
  return result.next;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 这是 ai 的回答，就是使用归并排序的方式
/* 
为了对链表进行排序，可以使用归并排序算法，它的时间复杂度为 O (n log n)，并且不需要额外的数组空间，适合处理链表结构。
归并排序的核心思想是分治法：将链表分成两半，分别排序后再合并。

方法思路
分割链表：使用快慢指针找到链表的中间节点，将链表分为左右两部分。
递归排序：对左右两部分链表分别递归调用排序函数。
合并有序链表：将两个有序链表合并为一个有序链表。
*/
var sortList = function (head) {
  // 递归终止条件：空链表或只有一个节点
  if (!head || !head.next) {
    return head;
  }

  // 使用快慢指针找到链表的中间节点
  let slow = head;
  let fast = head.next;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // 分割链表为左右两部分
  const mid = slow.next;
  slow.next = null; // 断开左半部分

  // 递归排序左右两部分
  const left = sortList(head);
  const right = sortList(mid);

  // 合并两个有序链表
  return merge(left, right);
};

// 合并两个有序链表的辅助函数
function merge(l1, l2) {
  const dummy = new ListNode(0);
  let tail = dummy;

  while (l1 && l2) {
    if (l1.val < l2.val) {
      tail.next = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      l2 = l2.next;
    }
    tail = tail.next;
  }

  // 处理剩余节点
  tail.next = l1 ? l1 : l2;

  return dummy.next;
}